import bisect


def solve(arr):
    # assuming right is shorter
    res = 0
    stack = [(arr[0], 0)]
    for right, h in enumerate(arr):
        if right == 0:
            continue

        if h == stack[-1][0]:
            res = max(res, h * (right - stack[-1][1]))
            continue
        elif h > stack[-1][0]:
            stack.append((h, right))
            continue

        i = bisect.bisect_left(stack, (h, -1))
        left = stack[i][1]
        res = max(res, (right - left) * (h+1))
    return res


def largest_pool(arr):
    if len(arr) <= 1:
        return 0
    left_res = solve(arr)
    right_res = solve(arr[::-1])
    return max(left_res, right_res)


def test():
    def brutal(arr):
        result = 0
        for i in range(n - 1):
            for j in range(i, n):
                area = min(arr[i], arr[j]) * (j-i)
                result = max(result, area)
        return result

    import random
    for _ in range(1000):
        n = random.randint(0, 20)
        arr = [random.randint(0, 10) for _ in range(n)]
        res1 = largest_pool(arr)
        res2 = brutal(arr)
        if res1 != res2:
            print(arr)
            print(res1)
            print(res2)
            assert 0
test()
